package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

/**
 * 普通数组<br>
 * 数组、分治、动态规划<br>
 * 中等
 *
 * <h1>53. 最大子数组和</h1>
 *
 * <p>给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。</p>
 */
public class E13MaxSubArray {
    public static void main(String[] args) {
        E13MaxSubArray maxSubArray = new E13MaxSubArray();

        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        TimeCostUtil.timeCost("动态规划-精简方法", () -> maxSubArray.solution1(nums));

        int[] nums2 = DataGeneratorUtil.generateRandomIntArray(10000000, -1000, 1000);

        TimeCostUtil.timeCost("动态规划-原始方法", () -> maxSubArray.solution1_preOptimization(nums2));
        TimeCostUtil.timeCost("动态规划-精简方法", () -> maxSubArray.solution1(nums2));
        TimeCostUtil.timeCost("分治", () -> maxSubArray.solution2(nums2));
        TimeCostUtil.timeCost("前缀和", () -> maxSubArray.solution2(nums2));
    }

    // 动态规划-原始方法
    public int solution1_preOptimization(int[] nums) {
        int len = nums.length;
        // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }

        // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    // 动态规划-精简方法
    public int solution1(int[] nums) {
        // 当前状态只与前一个状态有关，压缩状态

        // dp 表示当前可以达到的最大子数组和

        // 初始化
        int dp = nums[0];
        int ans = dp;
        for (int i = 1; i < nums.length; i++) {
            dp = Math.max(dp + nums[i], nums[i]);
            if (dp > ans) ans = dp;
        }
        return ans;
    }

    // 分治
    public int solution2(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        return solution2SubArray(nums, 0, len - 1);
    }

    private int solution2SubArray(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        return max3(solution2SubArray(nums, left, mid),
                solution2SubArray(nums, mid + 1, right),
                maxCrossingSum(nums, left, mid, right));
    }

    private int max3(int num1, int num2, int num3) {
        return Math.max(num1, Math.max(num2, num3));
    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 一定会包含 nums[mid] 这个元素
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        // 左半边包含 nums[mid] 元素，最多可以到什么地方
        // 走到最边界，看看最值是什么
        // 计算以 mid 结尾的最大的子数组的和
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        // 右半边不包含 nums[mid] 元素，最多可以到什么地方
        // 计算以 mid+1 开始的最大的子数组的和
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }

    // 前缀和
    public int solution3(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int min = 0;
        int sum = 0;
        for (int i : nums) {
            sum += i;
            ans = Math.max(ans, sum - min);
            min = Math.min(min, sum);
        }
        return ans;
    }
}
